public class BinarySearchTree {

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }
    public TreeNode root=null;
    public boolean search(int val){
        if(root==null) return false;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val<val){
                cur=cur.right;
            } else if (cur.val>val) {
                cur=cur.left;
            }else {
                return true;
            }
        }
        return false;
    }
    public boolean insert (int val){
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
        }
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            } else if (cur.val>val) {
                parent=cur;
                cur=cur.left;
            }else {
                //二叉搜索树不能有相同的值
                //
                return false;
            }
        }
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        return true;
    }
    public void remove(int val){
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            } else if (cur.val>val) {
                parent=cur;
                cur=cur.left;
            }else {
                //删除的逻辑
            }
        }
    }
    private void removeNode(TreeNode parent,TreeNode cur){
        if(cur.left==null){//只有一个右孩子
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if(cur.right==null){//只有一个左孩子
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.right){
                parent.right=cur.left;
            }else{
                parent.left=cur.left;
            }
        }else{//左右孩子健全
            //左右孩子都在：
            //不能改变二叉树的结构
            //替罪羊的方法
            //有两个替罪羊：合适的替罪羊
            //找到替罪羊，就可以简化
            //从左右两个孩子往下都能找到替罪羊
            //
            TreeNode targetParent=cur;
            TreeNode target=cur.right;
            while(target.left!=null){
                targetParent=target;
                target=targetParent.left;
            }
            cur.val= target.val;
            if(target== targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right=target.right;//其实这也算一种特殊的，第一个就要删
            }
            //真的是很有思想，太厉害了，
            //
        }
    }
    //旋转降低树的高度：AVL树
    //红黑树：树有了颜色
    //旋转不会那么的多
    //
    //今天学的是最简单的二叉搜索树

    //key-val
    //MAP：地图：要对应起来，你必须要key-Val
//    纯K

}
